1. Field of the Invention
This invention relates to error detection in data processing system storage elements and, more particularly, to virtual encoding techniques for use in detecting failures in information maintained in said storage elements. Failures in devices used for accessing particular portions of said storage elements are also detectable via the virtual encoding techniques to be set out herein.
2. Description of the Prior Art
Use of encoding techniques over data about to be stored is a well-known approach to providing speedy error detection in information storage systems wherein single fault assumptions are valid.
In the reliability art, in general, it has become conventional to define a fault as a malfunction of a system component and a failure, or error, as a manifestation of a fault. Hence a single fault may result in multiple errors depending on the function of the faulty component.
Memory systems, in particular, are, in part, made up of certain components which, when faulty, give rise to multiple errors in the data handled therein. This is especially true of memory accessing circuits such as address decoders, where a single fault may give rise to multiple sections, or words, of the memory medium being simultaneously accessed. Under the multiple access situation, when attempting to read or write a first word, it becomes possible to inadvertently destroy the contents of a second word.
Prior art techniques utilizing coding to detect memory system errors are limited in that they operate on failures rather than faults. Many of these prior art schemes have successfully attacked the problems of detecting a predetermined assumed maximum number of errors in the stored data using approaches such as the well-known Hamming codes.
The incorrect accessing problem has also been solved in the prior art by providing virtual encoding of the memory word address in addition to the data to be stored. One such approach is found in U.S. Pat. No. 3,231,858 issued 25 Jan., 1966, to Tuomenoksa et al. wherein each memory word contains a single error correcting, double error detecting Hamming code computed over the concatenation of the word address and the data to be stored at that address. The code is "virtually" embedded because the address itself is never stored with the data. This scheme detects up to two errors in the data or address information but is incapable of recognizing "multiple" (i.e., in this case, more than two) errors resulting from multiple access.
The task of detection of multiple errors resulting from multiple accessing has, in the past, been assigned to rather unwieldy analog techniques. One such approach is found in U.S. Pat. No. 3,157,860 issued 17 Nov., 1964, to Batley, wherein supplementary magnetic cores are inserted in a magnetic memory's access lines for determining, via monitoring of the access currents, whether or not multiple access has occurred. Access driver current can be summed and compared with a preset allowable threshold determined by a suitable reference device such as a Zener diode, as suggested in an article by Szygenda and Flynn in "Failure Analysis of Memory Organization for Utilization in a Self-Repair Memory System," IEEE Transactions on Reliability, Volume R-20, Number 2, Pages 64-70, May, 1971.
An assumption as to the nature of multiple memory system failures that is now commonly accepted in the art is that such failures manifest themselves in unidirectional errors (i.e., all the errors will be either false zeros or false ones, but not a mixture of the two). As a result of this assumption, many prior art approaches have opted for use of fixed weight, or so-called m-out-of-n, codes for detection of multiple-unidirectional errors. An m-out-of-n code is one in which all valid code words have exactly m bits equal to 1 out of the total of n bits. Although such constant weight codes can detect all unidirectional errors, they have the disadvantage of being non-separable. A code is termed "separable" only if the data bits are distinct from those bits provided for error detection. In the fixed weight codes, it is the bit pattern itself that provides error detection, and no such separation between data and check bits is possible. Separability is desirable when one wishes to easily add error detection features to an existing system without forcing a change in the existing memory word alphabet. Another salient feature of separable codes is the fact that one may choose a variable number of words over which the encoding is to take place.
Recent evolution of solid state memories constructed on integrated circuit chips has led to a similar problem with prior art failure detection schemes, since the assumption that a typical fault will cause a single bit failure is no longer valid. Analysis has shown that the most likely faults in semiconductor memory chips give rise to multiple unidirectional failures. This failure pattern analysis is discussed in more detail in "Design of a Self-Checking Microprogram Control," IEEE Transactions on Computers, Volume C-22, Number 3, Pages 255-262, March, 1973. In the case of magnetic memory systems, unidirectional errors are caused by multiple access, while in semiconductor memories, such failures are a result of the inherent compact construction of the memory medium itself in addition to any multiple access problems that may arise.
Hence a problem in the prior art is seen in connection with detecting multiple unidirectional failures in data processing memory subsystems without resort to either unwieldy analog methods or to use of non-separable codes.